I. Technical Field
This invention pertains to wireless telecommunications, and particularly to detection of information transmitted over a radio interface.
II. Related Art and Other Considerations
In a typical cellular radio system, a wireless terminal communicates via a radio access network (RAN) to one or more core networks. The wireless terminal can be a mobile station (also termed “user equipment unit” (“UE”) or “mobile terminal”) such as a mobile telephone (“cellular” telephone) and laptop with mobile termination, and thus can be, for example, a portable, pocket, hand-held, computer-included, or car-mounted mobile device which communicates voice and/or data with the radio access network. Alternatively, the wireless terminal can be a fixed wireless device, e.g., fixed cellular devices/terminal which is part of a wireless local loop or the like.
The radio access network (RAN) covers a geographical area which is divided into cell areas, with each cell area being served by a base station. A cell is a geographical area where radio coverage is provided by the radio base station equipment at a base station site. Each cell is identified by a unique identity, which is broadcast in the cell. The base stations communicate over the air interface (e.g., radio frequencies) with the wireless terminal within range of the base stations. In the radio access network, several base stations are typically connected (e.g., by landlines or microwave) to a radio network controller (RNC). The radio network controller, also sometimes termed a base station controller (BSC), supervises and coordinates various activities of the plural base stations connected thereto. The radio network controllers are typically connected to one or more core networks.
Thus, wireless communications involve transmission of information over an air or radio interface from a transmitter station to a receiver station. For example, a mobile transmitter station (e.g., mobile station) may send a message on an uplink channel to a receiver unit such as a base station. Conversely, a transmitter unit in the form of a base station may send a message on a downlink channel to a receiver of a mobile station, or even to receivers in plural mobile stations.
In some instances a transmission between stations includes a particular sequence of samples. The sequence can be used to identify a particular transmitting station and/or to facilitate synchronization between the transmitting unit of one station and the receiving unit of another station. When associated for such purposes with a particular station, the sequence is known as a “signature sequence”. For example, a base station may have a particular signature sequence included in certain transmissions to distinguish that particular base station from other base stations whose signals may be also be received by mobile stations. Similarly, a mobile station may be assigned a certain signature sequence, at least temporarily (e.g., per connection, while in a specified cell), so that when the signature sequence is included in a wireless transmission on the uplink to a base station node, the base station node can determine that the transmissions emanated from that mobile station rather than other mobile stations in the cell of the base station node.
The received signal corresponding to a signature sequence s[n] at the output of a time-frequency selective channel is given by Expression (1).
                                          r            ⁡                          [              n              ]                                =                                                    ∑                                  τ                  =                  0                                                  τ                                      m                    ⁢                                                                                  ⁢                    ax                                                        -                    1                                                              ⁢                                                          ⁢                                                ∑                                      v                    =                    0                                                        v                                          m                      ⁢                                                                                          ⁢                      ax                                                              -                      1                                                                      ⁢                                                                  ⁢                                                      h                    ⁡                                          [                                              τ                        ,                        v                                            ]                                                        ⁢                                      s                    ⁡                                          [                                              n                        -                        τ                                            ]                                                        ⁢                                      ⅇ                                          j                      ⁢                                                                        2                          ⁢                          π                          ⁢                                                                                                          ⁢                          vn                                                N                                                                                                                  +                          z              ⁡                              [                n                ]                                                    ,                            (        1        )            In Expression (1), z[n] is the Additive White Gaussian Noise (AWGN) and h[τ, ν] is the channel's delay-Doppler response with support (0≦τ<τmax, 0≦ν<νmax). The maximum delay-Doppler spread (τmax, νmax), is usually a small fraction of the sequence length N.
The detection of a signature sequence is traditionally achieved by calculating a likelihood metric that is generally related to the inner product between the received signal and a hypothesis of the transmitted signature sequence. Using r[n] to be the received signal and s[n] to be a hypothesized signature sequence, a typical example decision metric is given by Expression (2).
                              γ          =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          r                ⁡                                  [                  n                  ]                                            ⁢              s              *                              [                n                ]                                                    ,                            (        2        )            In Expression (2) N is the length of the sequence. In a case when the channel is time-dispersive, or when the timing offset is unknown, the inner product is evaluated over various lag τ by Expression (3):
                              γ          =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          r                ⁡                                  [                  n                  ]                                            ⁢              s              *                              [                                  n                  -                  τ                                ]                                                    ,                            (        3        )            Further, more if the channel is frequency dispersive, or if the frequency offset is unknown, the inner product need to be evaluated over multiple hypotheses of Doppler frequency ν as shown in Expression (4).
                    γ        =                              ∑                          n              =              0                                      N              -              1                                ⁢                                    r              ⁡                              [                n                ]                                      ⁢            s            *                          [                              n                -                τ                            ]                        ⁢                          ⅇ                                                -                  j                                ⁢                                                      2                    ⁢                    π                    ⁢                                                                                  ⁢                    vn                                    N                                                                                        (        4        )            
The computation of these inner products, or correlations, needs to be carried out for each hypothesis, e.g. each candidate or guess, of the signature sequence. For the purpose of identifying a large number of communicating devices in application such as random access shown in Ericsson contribution “E-UTRA Random Access Preamble Design,” TSG-RAN WG1 #44bis, R1-06998, Athens, Greece, Mar. 27-31, 2006 (incorporated herein by reference), the computation complexity may be exceedingly high, especially when the signature sequence set lacks a common structure.
A good signature sequence set can be derived from a single properly chosen base sequence by artificially introducing circular delay-Doppler shifts to the base sequence. The detection of a sequence then becomes the detection of the artificially introduced delay-Doppler shift assigned to that sequence in the presence of the channel-induced delay-Doppler shifts and can be accomplished by a single two-dimensional delay-Doppler correlator given in Expression. (4).
Assuming that the only channel information available is the maximum delay-Doppler spread (τmax, νmax), the optimal detection of a single sequence is to evaluate the generalized likelihood function of Expression (6).
                              γ          =                                    ∑                              τ                =                0                                                              τ                                      ma                    ⁢                                                                                  ⁢                    x                                                  -                1                                      ⁢                                          ∑                                  υ                  =                  0                                                                      υ                                          m                      ⁢                                                                                          ⁢                      ax                                                        -                  1                                            ⁢                                                                                      I                    ⁡                                          [                                              τ                        ,                        v                                            ]                                                                                        2                                                    ,                            (        6        )                                          I          ⁡                      [                          τ              ,              v                        ]                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                    r              ⁡                              [                n                ]                                      ⁢                                          s                *                            ⁡                              [                                  n                  -                  τ                                ]                                      ⁢                          ⅇ                              -                                                      j2π                    ⁢                                                                                  ⁢                    vn                                    N                                                                                        (        7        )            In Expression (6), Expression (7) is the delay-Doppler image defined over 0≦τ<N, 0≦ν<N. The metric of Expression (6) is then evaluated for each possible hypothesis of the signature sequence and compared with a threshold to determine whether a user is present in the system.
In one example embodiment proposed in simultaneously-filed U.S. patent application Ser. No. 11/760,654, entitled “NOVEL SIGNATURE SEQUENCES AND METHODS FOR TIME-FREQUENCY SELECTIVE CHANNEL”, each user is assigned a unique signature sequence which is a member of a specially constructed set of sequences. This special set of sequences is derived from a same base sequence of length N. However, the signature sequences of the set, assigned to different stations, differ in that the base sequence has been shifted with a unique (preferably unique circular) delay-Doppler shift. Thus the signature sequence is exemplified by Expression (8).
                                                        s                              l                ,                m                                      ⁡                          [              n              ]                                =                                    s              ⁡                              [                                  n                  -                                      l                    ⁢                                                                                  ⁢                                          τ                      d                                                                      ]                                      ⁢                          ⅇ                              -                                                      2                    ⁢                    π                    ⁢                                                                                  ⁢                                          mv                      d                                        ⁢                    n                                    N                                                                    ,                            (        8        )            In Expression (8), (τd, νd) is a minimum delay-Doppler separation between any pair of derived sequences and (l, m) is the unique identification index assigned to a user, e.g., to a station. As long as the minimum delay-Doppler separation of these artificially introduced shifts is greater then the maximum shift (τmax, νmax) introduced by the channel, multiple sequences can be distinguished even after passing through the channel.
Since the sequence identification is incorporated into the channel's delay-Doppler spread, the detection metric for the delay-Doppler shifted sequences can be calculated by first evaluating the delay-Doppler images given in Expression (7) and then summing the output over the appropriate area for all hypotheses of [l,m] as shown in Expression (9).
                              γ          ⁡                      [                          l              ,              m                        ]                          =                              ∑                          τ              =                              l                ⁢                                                                  ⁢                                  τ                  d                                                                                    l                ⁢                                                                  ⁢                                  τ                  d                                            +                              τ                                  ma                  ⁢                                                                          ⁢                  x                                            -              1                                ⁢                                    ∑                              v                =                                  mv                  d                                                                              mv                  d                                +                                  v                                      m                    ⁢                                                                                  ⁢                    ax                                                  -                1                                      ⁢                                                                                                  τ                    ⁡                                          [                                              τ                        ,                        v                                            ]                                                                                        2                            .                                                          (        9        )            
For an arbitrary set of sequences, computation of the detection metric in Expression (9) for all hypotheses may be prohibitively complex. For the specially constructed delay-Doppler shifted sequence set, the computation is structurally simpler since only one base sequence needs to be stored in memory.
The brute force, direct calculation of the delay-Doppler image given in Expression (7) for all points in the plane takes N length-N DFTs. Additionally, there are N multiplications for each delay index τ preceding the DFT. Therefore, assuming that N is a power of 2, approximately N(N+N log2 N) multiplications are required to evaluate the entire delay-Doppler image.
What is needed, therefore, and an object of the present invention, are improved method, apparatus, system, and techniques for reducing complexity of signature sequence detection.